package generator.test.examples.nqueens;


@SuppressWarnings("serial")
public final class NQueens implements
        NQueensInterface, java.io.Serializable {

    static final int THRESHOLD = 4;
    NQueensInterface selfDependency;
    /** 
     * We need a global variable holding the result of search.
     * Check this to see if it is nonnull,
     * if so, returning early because a result has been found.
     * In a more serious program, we might use a fancier scheme
     * to reduce read/write pressure on this variable.
     **/

    public byte[] nqueens(byte[] sofar, int row, int size) {
        byte[][] result = null;
        if (row >= size) { // done
            return sofar;
        }
        if (row < THRESHOLD) {
            result = new byte[size][];
        }
        for (int q = 0; q < size; q++) {
            // Check if can place queen in column q of next row
        	boolean cut = false;
            for (int i = 0; i < row && !cut; i++) {
                int p = sofar[i] - q;
                if (p == 0 || p == (row - i) || p == -(row - i)) {
                    cut = true;
                }
            }
            if (!cut) {
            	// Fork to explore moves from new configuration
            	if (row < THRESHOLD) {
            		byte[] next = new byte[size];
            		System.arraycopy(sofar, 0, next, 0, row);
            		next[row] = (byte) q;
            		byte[] jgrimvar = this.getSelfDependency().nqueens(next, row + 1, size);
            		result[q] = jgrimvar;
            	} else {
            		// don't spawn anymore
            		byte[] res;
            		sofar[row] = (byte) q;
            		res = nqueens(sofar, row + 1, size);
            		if (res != null)
            			return res;
            	}
            }
        }
        if (row < THRESHOLD) {
            for (int q = 0; q < size; q++) {
                if (result[q] != null)
                    return result[q];
            }
        }
        return null;
    }

	public NQueensInterface getSelfDependency() {
		return selfDependency;
	}

	public void setSelfDependency(NQueensInterface selfDependency) {
		this.selfDependency = selfDependency;
	}

	public boolean checkResult(byte[] board) {
		boolean found;
        for (int row = 0; row < board.length; row++) {
            found = false;
            boolean cut = false;
            for (int q = 0; q < board.length && !cut; q++) {
                // Check if can place queen in column q of next row
                for (int i = 0; i < row; i++) {
                    int p = board[i] - q;
                    if (p == 0 || p == (row - i) || p == -(row - i)) {
                        cut = true;
                    }
                }
                found = true;
            }
            if (!found)
                return false;
        }
        return true;
    }

    public void run() {

        int size = 10;
        long start, end;
        double time;
         System.out.println("nqueens " + size + " started");

        if (size <= 3) {
            System.out.println("There is no solution for board size <= 3");
            System.exit(66);
        }

        byte[] board = null;
        start = System.currentTimeMillis();
        board = this.getSelfDependency().nqueens(new byte[size], 0, size);
        end = System.currentTimeMillis();

        if (!this.checkResult(board)) {
            System.out.println("application time nqueens (" + size
                    + ") gave WRONG RESULT");
            System.out.println("application result nqueens (" + size
                    + ") gave WRONG RESULT");
            System.exit(1);
        }

        System.out.print("application result nqueens (" + size + ") = ");

        for (int i = 0; i < board.length; ++i) {
            System.out.print(" " + board[i]);
        }
        System.out.println();

        time = end - start;
        time /= 1000.0;

        System.out.println("application time nqueens (" + size + ") took "
                + time + " s");
    }
}